Fundamental Drawing Algorithms in Computer Graphics - Chapter 4 - [Part 1]

مهم قبل ما تبدا
  • الشابتر ده طويل ف اضطريت اقسمه لجزئين , وكمان الدكتور حاطط قوانين من غير امثلة (هو نزل مثالين بس علي المنصه) انا معرفش بصراحه هيجيب مسائل علي الحاجات دي ولا لا بس انا جبت امثلة كراسة العملي وشرحتها احتياطي.
  • هتلاقي جداول وكلام كتير وطويل متتخضش الموضوع سهل اوي هو كل مشكلته انه طويل بس لو بصيت علي الامثله هتفهمها لوحدك اصلا.
  • هتلاقي اكواد العملي تحت كل الجورزم للي عايز يجرب بس حسب كلام الدكتور هيا مش علينا حفظ.
  • طول بالك وقول بسم الله
مقدمه

الشابتر ده هنقسمه لجزئين: الجزء الأول (اللي إحنا فيه) عن Line Drawing Algorithms، والتاني عن Circle Drawing Algorithms.

  • الـ Drawing Algorithms هي الخوارزميات اللي بتخلي الكمبيوتر يرسم أشكال أساسية على شاشة مبنية من pixels.
  • هنفهم ليه بنحتاج نحول الوصف الرياضي للشكل لمجموعة pixels، وبعدين هنتعمق في line drawing algorithms زي Direct Line Equation, DDA, و Bresenham — مع أمثلة تطبيقية لكل واحد.

1) Introduction to Drawing Algorithms

  • في Computer Graphics، رسم الأشكال الأساسية زي الخطوط والدواير حاجة اساسية عشان نعرف نرسم اي object.
  • غالبا الشكل بيتوصف رياضيا بأرقام:
    • الخط بيتحدد بنقطة بداية ونقطة نهاية.
    • الدائرة بتتحدد بمركز ونصف قطر.
  • المشكلة إن الشاشة مش continuous زي الرياضيات، هيا عبارة عن grid من pixels, عشان كده محتاجين نحول الوصف الرياضي ده لـ pixels تتلون على الشاشة.
الفكرة الأساسية

الـ Drawing Algorithm بيقرر أنهي pixels تتلون عشان الشكل الرياضي يبان أقرب حاجة للشكل الحقيقي على شاشة raster.


2) Geometric Primitives and Mathematical Description

  • خدنا الشابتر الي فات الـ Geometric Primitives وعرفنا انها الأشكال الأساسية اللي بنبني منها الرسومات, زي:
    • Line
    • Circle
    • Polygon
    • Curve
  • كل primitive ليه وصف رياضي:
    • الـ Line: بيتحدد بـ start point و end point.
    • الـ Circle: بيتحدد بـ center و radius.
  • الوصف الرياضي ده بيبقى في abstract coordinate space، يعني وصف دقيق على مستوى الرياضيات مش على مستوى الـ pixels.

3) Raster Displays and Rasterization

definition

Rasterization is the process of converting continuous mathematical shapes into a set of discrete pixels.

  • الشاشات الحديثة بتبقي Raster-Based، يعني الصورة فيها عبارة عن pixels مترتبة في grid مستطيل (عشان كده الشكل الرياضي مينفعش يتعرض مباشرة على الشاشة).
  • لازم الاشكال الرياضية دي تتحول لبكسلات.

Pixel-Based Representation

  • عشان نفهم الموضوع، تخيل ان عندنا grid وعايزين نرسم vertical line (خط رأسي) من (2, 9) لـ (2, 16):
    • ا x = 2 ثابت.
    • ا y بيتحرك من 9 لـ 16.
  • في الرياضة الفرق صغير ,بس في الشاشات الحقيقية الموضوع كبير، الـ resolutions ممكن يعدي 1000 × 1000 pixels.
  • عشان كده الالجورزمز لازم تبقى accurate و efficient، خصوصا في real-time rendering.

4) What are Drawing Algorithms?

definition

Drawing algorithms are fundamental techniques used in computer graphics to render shapes, lines, curves, and other geometric primitives on a screen or image.

  • الـ Drawing Algorithms بتحدد إزاي lines و circles و curves وباقي primitives تتحول لـ pixels.
  • الهدف إن الشكل النهائي يبقى قريب قدر الإمكان من الشكل الرياضي المقصود.
  • بتستخدم في:
    • Video games
    • Simulations
    • Scientific visualization
    • Graphic design tools

5) Essential Drawing Algorithms

Category Algorithms
Line Drawing DDA, Bresenham's Line Algorithm
Circle Drawing Basic Equation Method, Midpoint Circle Algorithm, Bresenham's Circle Algorithm, Parametric Circle Algorithm
Polygon Drawing Scan-line Fill, Boundary Fill, Flood Fill
Curve Drawing Bézier Curve, Spline Curve
Anti-Aliasing Xiaolin Wu's Line Algorithm, Supersampling
Clipping Cohen-Sutherland, Liang-Barsky, Sutherland-Hodgman
Transformation Translation, Rotation, Scaling, Shearing
Note

الشابتر بيركز على implementation توضيحي واحد لكل algorithm عشان يشرح الفكرة الأساسية، والتطبيقات والكود موجودين في كراسة العملي.


6) Line Drawing Algorithms

definition

Line drawing algorithms approximate straight line segments on discrete, pixel-based displays.

  • زي ما قلنا قبل كده، الشاشة دي عبارة عن Grid من البيكسلات، فعشان ترسم خط مستقيم مايل، مستحيل يجي بالظبط على البيكسلات، عشان كده بنعمل تقريب (Approximation).
  • الـ algorithm الأساسية زي الـ Digital Differential Analyzer (DDA) والـ Bresenham's algorithm بترسم الخط بلون واحد، وده بيعمل المشكله الي شوفناها قبل كده الـ aliasing . وبنستخدم الـ Anti-aliasing اللي بتدمج ألوان البيكسلات اللي حوالين الخط عشان تنعم الحواف دي.

7) Direct Use of Line Equation

Concept

  • دي أبسط طريقة ممكن تفكر فيها، وهي إننا نستخدم معادلة الخط المستقيم العادية جداً اللي درسناها في الرياضة في ثانوي.
  • عشان نرسم خط باستخدام الـ Slope-intercept form، بنمشي على الخطوات دي:
    1. بنحسب الميل (Slope) اللي هو والجزء المقطوع من محور الصادات (Intercept) اللي هو .
    2. بنعمل لوب او بنلف على قيم الـ اللي بين نقطة البداية والنهاية.
    3. لكل قيمة ، بنحسب قيمة الـ اللي بتقابلها من المعادلة:
y = mx + c
  • في الآخر بنعمل Plot (رسم) للبيكسل بعد ما نعمل التقريب (Rounding) لقيم

Advantages

  • سهلة ومباشرة.
  • ممكن تتعامل مع : positive, negative, zero , or undefined slopes .

Application in Computer Graphics:

  • معادلة الخط المستقيم بنستخدمها كأساس في خوارزميات تانية زي:
    • ا DDA (Digital Differential Analyzer).
    • ا Bresenham's Line Algorithm (using an implicit form).

Disadvantages

  • بتعتمد على Floating-Point Arithmetic (عمليات الكسور العشرية دي بطيئة شوية للكمبيوتر وممكن تدخلنا في rounding errors).
  • أقل كفاءة من algorithms مبنية على integers زي Bresenham.

Key Observations

  • الخط ممكن يتمثل بأكتر من شكل رياضي.
  • في الـ Raster graphics، بنختار البيكسلات الأقرب لمسار الخط المثالي.
  • لازم نحافظ على الـ Aspect ratio عشان الشكل ميبقاش مشوه.

مثال من كراسة العملي علي Line Equation

عايزين نرسم خط بين النقطتين (2,2) و (10,6) باستخدام معادلة الخط المستقيم المباشرة .

Step 1: Initial Calculations

  • أول حاجة بنعملها إننا بنحسب الـ Slope (الميل) اللي بنرمزله بـ m، والـ Y-intercept (الجزء المقطوع من محور الصادات) اللي بنرمزله بـ c.

  • حساب الميل ():

    • هنعوض في القانون ده عشان نجيب الميل:
  • حساب الـ Y-intercept ():

    • هنعوض بنقطة البدايه 2,2 في المعادلة c = y - mx (تقدر تعوض بأي نقطة عادي ) عشان نجيب c:
  • المعادلة النهائية للخط:

    • كده معانا c, m هنعوض بقي في القانون y = mx + c
    • يبقى المعادلة اللي هنعوض فيها لكل بيكسل هي:
  • تحديد اتجاه اللوب (Condition):

  • بما إن التغير في السينات أكبر من التغير في الصادات ، يبقى ده Shallow line (خط مائل للأفقي). عشان كده إحنا هنعمل Loop على الـ (هنزود الـ بمقدار 1 في كل خطوة)، ونحسب الـ من المعادلة.

لو Δy هي الأكبر، يبقى هنمشي وراها. يعني هنعمل Loop على محور الصادات (هنزود الـ بمقدار 1 في كل خطوة), ونحسب x بالقانون ده

Step 2: Iterative Table

  • هنا بقى بنمسك قيم X من أول 2 لحد 10، وفي كل مرة نعوض في المعادلة بتاعتناy = 0.5x + 1عشان نجيب قيمة الـ y.
  • وطبعا عشان دي أرقام عشرية (Floating-point)، لازم نعمل Rounding (نقرب) في الخر عشان نجيب الـ Pixel الصح.
Step x (Loop variable) y (Calculated: 0.5x+1) Pixel (after rounding)
0 2 (2, 2)
1 3 (3, 3)
2 4 (4, 3)
3 5 (5, 4)
4 6 (6, 4)
5 7 (7, 5)
6 8 (8, 5)
7 9 (9, 6)
8 10 (10, 6)

Final Pixels:

(2,2), (3,3), (4,3), (5,4), (6,4), (7,5), (8,5), (9,6), (10,6)

Chat GPT Image May 29 2026 07 06 07 PM

8) Digital Differential Analyzer (DDA)

definition

DDA is a line-drawing algorithm that incrementally computes pixel positions using floating-point arithmetic.

Purpose

  • ده بقى Algorithm أذكى شوية. الغرض بتاعه إنه يقرب الخط المستقيم من خلال حساب إحداثيات البيكسلات اللي في النص خطوة بخطوة (Step-by-step).

Key Idea

  • الفكرة الأساسية إننا بنزود الـ X أو الـ Y بخطوات صغيرة جداً بناءً على ميل الخط، وبنختار الاتجاه الغالب (Dominant direction) عشان نقلل الحسابات.
  • يعني بنمشي خطوة خطوة بدل ما نحسب المعادلة كلها من الصفر كل مرة.

Steps

  1. خد نقطتين: (x0, y0) و (x1, y1).
  2. احسب الفرق:
  1. حدد عدد الخطوات (ناخد القيمة الأكبر بين الـ والـ .):

  1. احسب مقدار الزيادة في كل خطوة:
  1. ابدأ من (x0, y0).
  2. في كل خطوة زود x بـ xinc و y بـ yinc.
  3. ارسم pixel عند الإحداثيات بعد rounding.

Advantages

  • سهل ومفهوم.
  • أسهل في التنفيذ من algorithms كتير.
  • أسرع من direct line equation عشان بيستخدم incremental generation.
  • بيقلل التكرار في الحسابات.

Disadvantages

  • لسه بيستخدم Floating-Point Arithmetic.
  • ممكن يراكم rounding errors.
  • ممكن يبقى أقل دقة عند endpoints.

مثال تطبيقي (DDA)

عايزين نرسم خط بين النقطتين (2,2) و (10,6) باستخدام DDA.

Step 1: Initial Calculations

  • أول حاجة بنعملها إننا بنجيب الفرق بين نقطة النهاية ونقطة البداية، عشان نعرف إحنا هنتحرك مسافة قد إيه على محور السينات والصادات,الفرق ده بنسميه Delta X و Delta Y.
Δx = 10 - 2 = 8
Δy = 6 - 2 = 4
  • بعد كده بنحسب الـ Steps. بناخد القيمة الأكبر بين الـ والـ . ليه؟ عشان نضمن إننا بنمشي خطوة خطوة على المحور الأطول، ويبقى الخط بتاعنا متصل ومفيش فيه فراغات.
steps = max(8, 4) = 8  
  • أخيراً، بنحسب الـ Increment (مقدار الزيادة). دي القيمة اللي هنزودها على الـ والـ في كل خطوة. بنقسم المسافة الكلية على عدد الخطوات.
x_inc = Δx / steps = 8 / 8 = 1
y_inc = Δy / steps = 4 / 8 = 0.5
  • يبقى كده إحنا فهمنا إن في كل خطوة، الـ هتزيد بمقدار 1 صحيح، بس الـ هتزيد بمقدار 0.5 (يعني نص خطوة).

Step 2: Iterative Table

  • هنا بنبدأ التنفيذ. بنبدأ من أول نقطة (2.0, 2.0) وكل دورة بنزود الـ x_inc والـ y_inc.
  • المشكلة اللي بتظهر هنا زي ما إنت شايف، إن الـ بتطلع بكسور زي 2.5 و 3.5. طبعا الشاشة مفهاش بكسل ونص, البيكسل ده مربع مش بيتقسم.
  • عشان كده إحنا لازم نعمل خطوة الـ Rounding (التقريب)، عشان نحول الكسور دي لأرقام صحيحة الجهاز يقدر يفهمها (مثلا 2.5 هتتقرب وتبقى 3).
Step x (before rounding) y (before rounding) Pixel (after rounding)
0 2.0 2.0 (2, 2)
1 3.0 2.5 (3, 3)
2 4.0 3.0 (4, 3)
3 5.0 3.5 (5, 4)
4 6.0 4.0 (6, 4)
5 7.0 4.5 (7, 5)
6 8.0 5.0 (8, 5)
7 9.0 5.5 (9, 6)
8 10.0 6.0 (10, 6)

Final Pixels

(2,2), (3,3), (4,3), (5,4), (6,4), (7,5), (8,5), (9,6), (10,6)
Chat GPT Image May 29 2026 03 05 21 PM

9) Bresenham's Line Algorithm

definition

Bresenham's Line Algorithm is an efficient integer-based algorithm for drawing straight lines on raster displays.

Key Idea

  • ا Bresenham بيستخدم Decision Parameter عشان نختار البيكسل اللي عليه الدور من غير أي كسور.
  • ميزته إنه بيتجنب floating-point calculations.
  • عشان كده أسرع وأنسب للهاردوير.

How It Works

  1. خد نقطتين: (x0, y0) و (x1, y1).
  2. احسب:
Δx = x1 - x0
Δy = y1 - y0
  1. حدد نوع الخط (بنحدد ميل الخط عشان نعرف هنمشي على أي محور):

    • لو |Δy| <= |Δx| يبقى الخط Shallow، (يعني ميله خفيف وأقرب للأفقي).
    • لو |Δy| > |Δx| يبقى الخط Steep، (يعني ميله حاد وأقرب للرأسي).
  2. استخدم الـdecision parameter الي هو p:

    • في shallow line:
p = 2Δy - Δx
  • في steep line:
p = 2Δx - Δy
  1. بنبدأ من أول نقطة ,وفي كل خطوة بنحدث معامل القرار وبنرسم البيكسل اللي بعده.

مثال تطبيقي (Bresenham)

عايزين نرسم نفس الخط بين النقطتين (2,2) و (10,6) بس المرة دي باستخدام خوارزمية Bresenham.

Step 1: Initial Values

  • اول حاجة بنحدد نقط البداية والنهاية، وبنجيب الفرق بينهم.
x0 = 2, y0 = 2
x1 = 10, y1 = 6
  • نحسب الـ Delta X والـ Delta Y:
Δx = 10 - 2 = 8
Δy = 6 - 2 = 4
  • بما إن Δx > Δy، يبقى الخط ده ميله خفيف (Shallow line)، وعشان كده إحنا هنعمل Iterate (نلف) على محور السينات x (يعني الـ x هتزيد دايما بـ 1)، والقرار كله هيبقى: هل نزود الـ y ولا نسيبها زي ما هي؟

Step 2: Decision Parameter

  • عشان ناخد القرار ده من غير ما نستخدم أي كسور، بنحسب حاجة اسمها Decision Parameter (معامل القرار) وبنرمزله بـ p. أول قيمة ليه بنحسبها كده:
p0 = 2Δy - Δx = 2(4) - 8 = 8 - 8 = 0
  • بعد كده في كل خطوة، بنبص على قيمة الـ p وبناءً عليها بنقرر:

  • لو p ≥ 0: الـ y بتزيد بـ 1، وبنحسب الـ p الجديدة بالمعادلة دي:

p = p + 2Δy - 2Δx
  • لو p < 0: الـ y بتفضل ثابتة زي ما هي، وبنحسب الـ p الجديدة بالمعادلة دي:
p = p + 2Δy

Step 3: Iteration Table

  • لاحظ إن كل الحسابات هنا جمع وطرح لأرقام صحيحة (Integers)، مفيش أي Rounding ولا كسور خالص
  • لاحظ برده اننا بنزود الـ X كل مره بس الـ Y ساعات اه وساعات لا.
Step x y p (decision) Pixel
0 2 2 0 (2, 2)
1 3 3 -8 (3, 3)
2 4 3 0 (4, 3)
3 5 4 -8 (5, 4)
4 6 4 0 (6, 4)
5 7 5 -8 (7, 5)
6 8 5 0 (8, 5)
7 9 6 -8 (9, 6)
8 10 6 (10, 6)

Final Pixels

(2,2), (3,3), (4,3), (5,4), (6,4), (7,5), (8,5), (9,6), (10,6)
  • بما إن دي نفس النقط اللي طلعت من الـ DDA، فالرسمة هتكون هي هي بالظبط على الشبكة، بس الفكرة كلها إن الطريقة اللي وصلنا بيها للنقط دي أسرع بكتير ومفيهاش وجع دماغ الكسور.
Chat GPT Image May 29 2026 07 21 56 PM

مقارنة سريعة: DDA vs Bresenham

اااااااااااااااااااااااااااااااااا DDA Bresenham
الحسابات بيستخدم كسور (Floating-point) بيستخدم أعداد صحيحة (Integer-based)
التقريب (Rounding) محتاج rounding في كل خطوة مش محتاج rounding
السرعة أبطأ نسبيا أسرع
الدقة ممكن يراكم rounding errors دقيق

10) ملخص المحاضرة

كده خلصنا الجزء الأول

اتكلمنا في الجزء ده عن Drawing Algorithms - إزاي الكمبيوتر بيعمل Rasterization ويحول الأشكال الرياضية لـ Pixels على الشاشة.

بالنسبة لـ Line Drawing عرفنا 3 طرق:

  • ا Direct Line Equation (y = mx + c) - سهلة وبديهية بس فيها Floating-Point و Rounding Errors
  • ا DDA - بيحسب Incrementally خطوة بخطوة، أسهل من Direct بس لسه فيه Floating-Point ومحتاج Rounding
  • ا Bresenham's Line Algorithm - الأسرع عشان Integer-Based بالكامل وبيستخدم Decision Parameter، مش محتاج Rounding ولا كسور